The present invention relates generally to digital computers, and more specifically to a digital division circuit incorporated in the computers.
In a digital division operation, an N-bit dividend "A" is divided by an N-bit divisor "B" of nonzero value by repeatedly performing subtraction between them according to an algorithm known as the non-restoring method to derive an N-bit quotient "C" and N-bit remainder "D". If B is zero, the operation is treated as being invalid. The non-restoring method involves the steps of repeating subtractions N times by shifting registers. In the first step, the divident A and divisor B are set into a dividend register and a divisor register, respectively, and a remainder register is cleared to zero. In the second step, the divisor B is subtracted from data which comprises the lower (N-1) bits of the remainder register and the most significant bit of the dividend register. If the subtraction fails, a "0" is written into the least significant bit position of the dividend register and both dividend and remainder registers are shifted one bit to the left (toward the most significant bit position), so that the MSB of the dividend register is shifted out into the LSB of the remainder register. If the subtraction is successful, a "1" is written into the LSB of the dividend register and the dividend and remainder registers are both shifted one bit to the left, and the result of the subtraction is written into the remainder register. When the second step is repeated N times, the quotient of the division operation is obtained by the dividend register and the remainder of the division is obtained by the remainder register.
Since the digital calculation circuitry is required to meet the recent demands for higher performance and higher level of sophistication, the number of bits which can be treated has increased and, hence, the amount of hardware has increased significantly. To keep the hardware to a minimum, a proposal has been made to implement a subtractor with (N/2)-bit circuitry by separating N-bits operands into lower- and higher-bit segments and performing a subtraction first on the lower-bit segments and then on higher-bit segments and combining the results of the respective subtractions. However, subtractions must be performed 2N times and hence there is an increase in the calculation time.